//TIP To <b>Run</b> code, press <shortcut actionId="Run"/> or
// click the <icon src="AllIcons.Actions.Execute"/> icon in the gutter.
public class Main {
    //三步问题
    public int waysToStep(int n) {
        //处理边界值
        if(n == 1 || n == 2) {
            return n;
        }
        if(n == 3) {
            return 4;
        }
        int MOD = (int) 1e9 + 7;
        //创建dp表
        int[] dp = new int[n + 1];
        //初始化
        dp[1] = 1;
        dp[2] = 2;
        dp[3] = 4;
        //填表
        for(int i = 4;i <= n;i++) {
            dp[i] = ((dp[i - 1] + dp[i - 2]) % MOD + dp[i - 3]) % MOD;
        }
        //返回值
        return dp[n];
    }
    //使用最小花费爬楼梯
    public int minCostClimbingStairs(int[] cost) {
        //创建dp表
        int len = cost.length;
        int[] dp = new int[len + 1];
        //初始化
        dp[0] = dp[1] = 0;
        //填表
        for(int i = 2;i <= len;i++) {
            dp[i] = Math.min((dp[i - 1] + cost[i - 1]),(dp[i - 2] + cost[i - 2]));
        }
        //返回值
        return dp[len];
    }
    public static void main(String[] args) {

    }
}